package org.basis.algorithm.lru;

import java.util.HashMap;
import java.util.Map;

/**
 * 手写lru缓存，核心点：hash表 + 双向链表 实现增删改查时间复杂度O(1)
 * 假设缓存支持存储的key-value都是String类型的
 * LinkedHashMap 就是通过这个原理实现的
 *
 * @author wenpan 2024/03/06 23:05
 */
public class LruCache {

    /**
     * 缓存容量
     */
    private final int cap;
    /**
     * hash表，用于提升查询效率
     */
    private Map<String, DoubleList.Node> map = new HashMap<>();
    /**
     * 自定义双向链表，保证按照插入时间有序
     */
    private DoubleList list = new DoubleList();

    public LruCache(int cap) {
        this.cap = cap;
    }

    /**
     * 从缓存里获取元素
     */
    public String get(String key) {
        // 如果不存在，直接返回
        if (!map.containsKey(key)) {
            return null;
        }
        // 将该节点提升为最近访问
        makeRecently(key);
        //返回具体值
        return map.get(key).val;
    }

    /**
     * 往缓存里放入元素
     */
    public void put(String key, String value) {
        // 1、元素不存在
        if (!map.containsKey(key)) {
            // 检查是否缓存已经满了，满了的话要先淘汰最久没有访问的元素再插入
            if (map.size() >= cap) {
                // 淘汰最久未使用的元素
                removeFirst();
            }
            addRecently(key, value);
        } else {
            // 2、元素已存在，则直接将该节点移动到链表的头节点
            DoubleList.Node node = new DoubleList.Node(key, value);
            map.put(key, node);
            makeRecently(key);
        }
    }

    /**
     * 移除最久未使用的元素
     */
    private DoubleList.Node removeFirst() {
        // 移除最久未访问的节点
        DoubleList.Node node = list.removeFirst();
        // 同时也需要从map中移除
        map.remove(node.key);
        // 返回移除的节点
        return node;
    }

    /**
     * 添加最近使用
     */
    private void addRecently(String key, String value) {
        DoubleList.Node node = new DoubleList.Node(key, value);
        list.addLast(node);
        map.put(key, node);
    }

    /**
     * 将一个节点变为最近访问
     */
    private void makeRecently(String key) {
        DoubleList.Node node = map.get(key);
        // 提升到链表尾部
        list.remove(node);
        list.addLast(node);
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("[");
        for (Map.Entry<String, DoubleList.Node> entry : map.entrySet()) {
            builder.append("(").append(entry.getKey())
                    .append(",").append(entry.getValue().val).append(")").append(",");
        }
        builder.append("]");
        return builder.toString();
    }

    /**
     * 自定义双向链表
     */
    static class DoubleList {
        /**
         * 尾节点
         */
        private Node head;
        /**
         * 头节点
         */
        private Node tail;
        /**
         * 链表节点个数
         */
        private int size = 0;

        public DoubleList() {
            // 头尾节点置为亚元节点
            head = new Node(null, null);
            tail = new Node(null, null);
            // 定义头尾节点的关系
            head.next = tail;
            tail.pre = head;
        }

        /**
         * 添加节点，用尾插法，添加到链表尾部
         */
        public void addLast(Node node) {
            if (node == null) {
                return;
            }
            // 尾节点的上一个节点的next指针指向待添加的节点
            tail.pre.next = node;
            // 待添加的节点的pre指针指向tail节点的前一个节点
            node.pre = tail.pre;
            // 待添加节点的next指针指向tail节点
            node.next = tail;
            // tail节点的pre指针指向待添加的节点
            tail.pre = node;
            size++;
        }

        /**
         * 移除指定的节点
         * 注意：头尾节点禁止删除
         */
        public Node remove(Node node) {
            if (node == null) {
                return null;
            }
            // 当前节点的上一个节点的next指针指向当前节点的下一个节点
            node.pre.next = node.next;
            // 当前节点的下一个节点的pre指针指向当前节点的上一个节点
            node.next.pre = node.pre;
            size--;
            return node;
        }

        /**
         * 移除链表第一个元素（也就是最久未访问的元素）
         */
        public Node removeFirst() {
            // 没有元素可移除
            if (head.next == tail) {
                return null;
            }
            // 第一个元素
            Node first = head.next;
            // 头节点的next指针指向first节点的下一个节点
            head.next = first.next;
            // first节点的下一个节点的pre指针指向头节点
            first.next.pre = head;
            // 返回被移除的元素
            return first;
        }

        public int getSize() {
            return size;
        }

        // 链表节点，包含k-v
        public static class Node {
            /**
             * 节点的key
             */
            private String key;
            /**
             * 节点值
             */
            private String val;
            private Node pre;
            private Node next;

            public Node(String key, String val) {
                this.key = key;
                this.val = val;
            }
        }
    }

}
